#include <stdio.h>
#include <stdbool.h>
#include <windows.h>

#define MAX_K 3 // 缓冲轨道数量

void rearrangeTrain(int train[], int n, int k) {
    int buffer_tracks[MAX_K][n];    // 缓冲轨道
    int buffer_tracks_size[MAX_K];  // 缓冲轨道当前大小
    int nowOut = 1;                 // 下一个要输出的车厢编号

    // 初始化缓冲轨道
    for (int i = 0; i < k; i++) {
        buffer_tracks_size[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        int car = train[i];
        // 如果入轨中的车厢编号等于当前要输出的编号
        if (car == nowOut) {
            printf("输出车厢 %d\n", car);
            nowOut++;
            // 检查是否有缓冲轨上的车厢可以输出
            for (int j = 0; j < k; j++) {
                while (buffer_tracks_size[j] > 0 && buffer_tracks[j][0] == nowOut) {
                    printf("输出车厢 %d\n", buffer_tracks[j][0]);
                    // 将车厢从缓冲轨中移除
                    for (int m = 0; m < buffer_tracks_size[j] - 1; m++) {
                        buffer_tracks[j][m] = buffer_tracks[j][m + 1];
                    }
                    buffer_tracks_size[j]--;
                    nowOut++;
                }
            }
        } else {
            bool found = false;
            // 在每个缓冲轨中查找是否有当前要输出的车厢
            for (int j = 0; j < k; j++) {
                if (buffer_tracks_size[j] > 0 && buffer_tracks[j][0] == nowOut) {
                    printf("输出车厢 %d\n", buffer_tracks[j][0]);
                    // 将车厢从缓冲轨中移除
                    for (int m = 0; m < buffer_tracks_size[j] - 1; m++) {
                        buffer_tracks[j][m] = buffer_tracks[j][m + 1];
                    }
                    buffer_tracks_size[j]--;
                    nowOut++;
                    found = true;
                    break;
                }
            }
            // 如果在缓冲轨中没有找到当前要输出的车厢
            if (!found) {
                // 找到小于入轨中第一个车厢编号的最大队尾元素所在队列编号j
                int j = -1;
                for (int m = 0; m < k; m++) {
                    if (buffer_tracks_size[m] == 0 || buffer_tracks[m][buffer_tracks_size[m] - 1] < car) {
                        j = m;
                        break;
                    }
                }
                if (j != -1) {
                    // 将入轨中的车厢移到缓冲轨中
                    int p = buffer_tracks_size[j];
                    while (p > 0 && buffer_tracks[j][p - 1] > car) {
                        buffer_tracks[j][p] = buffer_tracks[j][p - 1];
                        p--;
                    }
                    buffer_tracks[j][p] = car;
                    buffer_tracks_size[j]++;
                } else {
                    printf("车厢无法重排，算法结束\n");
                    return;
                }
            }
        }
    }
    // 输出剩余缓冲轨道上的车厢和未入轨的车厢
    while (nowOut <= n + 1) {
        for (int j = 0; j < k; j++) {
            if (buffer_tracks_size[j] > 0 && buffer_tracks[j][0] == nowOut) {
                printf("输出车厢 %d\n", buffer_tracks[j][0]);
                // 将车厢从缓冲轨中移除
                for (int m = 0; m < buffer_tracks_size[j] - 1; m++) {
                    buffer_tracks[j][m] = buffer_tracks[j][m + 1];
                }
                buffer_tracks_size[j]--;
                nowOut++;
                break;
            }
        }
        if (nowOut <= n + 1) {
            printf("输出车厢 %d\n", nowOut);
            nowOut++;
        }
    }
}

int main() {
    SetConsoleOutputCP(65001);
    int train[] = {3, 6, 9, 2, 4, 1, 5, 7, 8};  // 入轨车厢编号
    int n = sizeof(train) / sizeof(train[0]);  // 入轨车厢数量
    int k = MAX_K;                             // 缓冲轨道数量
    rearrangeTrain(train, n, k);
    return 0;
}
